class Solution {
public:
    string longestPalindrome(string s) {
        
        int left=0,right=0;
        string ret;
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n,false));
        for(int len=1;len<=s.size();++len){
            for(int l=0;l+len-1<s.size();++l){
                int r=l+len-1;
                if(len==1){
                    dp[l][r]=true;
                }
                else if(s[l]==s[r]){
                    if(l+1==r){
                        dp[l][r]=true;
                    }
                    else{
                        dp[l][r]=dp[l+1][r-1];
                    }   
                }
                if(dp[l][r]){
                    if(r-l+1>right-left+1){
                        left=l;
                        right=r;
                    }
                }
            }
        }
        return s.substr(left,right-left+1);
    }
};
